Aminet 7/Aminet 7 - August 1995.iso/Aminet/docs/misc/ConcNews.lha/news/general.programming/comp.programming_1572_000022.msg

Text File | 1994-11-27 | 1.6 KB | 39 lines

Newsgroups: comp.programming
Path: dd.chalmers.se!news.chalmers.se!sunic!EU.net!howland.reston.ans.net!torn!newshub.ccs.yorku.ca!oz
From: [e-mail] (Ozan S. Yigit)
Subject: Re: Hash function for strings
In-Reply-To: [e-mail]'s message of 3 Mar 1994 17:39:59 GMT
Message-ID: <[e-mail]>
Sender: [e-mail] (USENET News System)
Organization: The Electric Skillet
References: <[e-mail]>
Date: Thu, 3 Mar 1994 20:54:16 GMT
Lines: 27

AMUNDSEN JARLE/3AA/D:

   I am trying to find a good hash function for strings, names that is, and
   wonder if anyone has an idea on how good such a function can hash. Given
   that the keys are not known in advance.

there are several good multiplicative ones, eg.

        33      due to dan bernstein [h = (h << 5) + h + c]
        131     due to gonnet/baeza-yates ("Handbook")
    65599    due to me (sdbm) [h = (h << 6) + (h << 16) - h + c]

there are also a bunch of scramble-type functions, eg. peter honeyman's
crc-hash routine from pathalias, or the one from lcc [str and list mgmt
module]. have you looked at those?

   The function I found to be best, starts at the end of the string and
   recursively shifts the hash of the previous character n times to the left and
   subtracts m, and adds the shift and subtraction of the current character.

is n a constant or the index of the current char? m is the table size?

oz
---
C++ was invented because Vogon poetry | electric: [e-mail]
wasn't destructive enough. -anonymous | ph:[416] 736 2100 x 33976